\section{Problem 1}

	The following parameters for a B-tree are used in that problem :\\

	\begin{tabular}{|l|c|r|}
	\hline
		\textbf{Description} & \textbf{Notation in formula} & \textbf{Value}\\
	\hline
		Number of records to be stored & $numberOfRecords$ & $3 \times 10^{10}$\\
	\hline
		Size of a record & $recordSize$ & 380 bytes\\
	\hline
		Size of a pointer to B-tree node & $pointerSize$ & 6 bytes\\
	\hline
		Page size & $pageSize$ & 8192 bytes\\
	\hline
	\end{tabular}

	\subsection*{Question a}
	
		Maximum order, i.e. maximum number of pointers in a single vertex, of a B-tree is given by the following formula : 
		\begin{equation}
			n = \dfrac{pageSize + recordSize}{recordSize + pointerSize}
			\label{eq:maxorder}
		\end{equation}
		In a single vertex containing $n$ pointers, there are $n-1$ records. Equation \ref{eq:maxorder} applied to our case gives :
		\begin{equation*}
			n = \dfrac{8192 + 380}{380 + 6} =  22,207253886 \simeq 22
		\end{equation*}
		
		\fbox{Answer : there are $n - 1$, i.e. \textbf{21} records in a single vertex.}
		
	\subsection*{Question b}
	
		In order to compute $d_{max}$ (the maximum depth of the B-tree), it is necessary to know two parameters :
		\begin{itemize}
			\item $m$, number of records in the root vertex.
			\item $r$, number of records in all other vertex.
		\end{itemize}
		$d_{max}$ is reached for a B-tree which has minimum density, i.e. when there are as few  possible records per vertex. That condition means :
		\begin{displaymath}
			\left\lbrace
			\begin{array}{r c l}
					m & = & 1\\
					r & = & \dfrac{n - 1}{2}
			\end{array}
			\right.
		\end{displaymath}
		
		Then the following equation gives $d_{max}$ :
		\begin{equation}
			d_{max} \leq \dfrac{ln\left(\dfrac{numberOfRecords + 1}{m + 1}\right)}{ln(r + 1)}
			\label{eq:maxdepth}
		\end{equation}
		
		So applied to our case we have the following system : 
		\begin{displaymath}
			\left\lbrace
			\begin{array}{r c l}
				m & = & 1\\
				r & = & \dfrac{21}{2} \simeq 11\\
				d_{max} & \leq & \dfrac{ln\left(\dfrac{3 \times 10^{10} + 1}{1 + 1}\right)}{ln(11 + 1)} \simeq 9,429455243
			\end{array}
			\right.
		\end{displaymath}
		
		Like $d_{max}$ is an integer, its value can not be superior to 9.\\
		
		\subsection*{Question c}
		
		The real value of $r$ for the total number of records per vertex is given by the following formula :\\
		\begin{equation}
			r = \sqrt[d_{max}]{\dfrac{numberOfRecords + 1}{m + 1}} - 1
			\label{eq:avgrecordsmax}
		\end{equation}
		
		Numerical application :\\
		\begin{displaymath}
			r = \sqrt[9]{\dfrac{3 \times 10^{10} + 1}{1 + 1}} - 1 = 12,5106675161
		\end{displaymath}
		
		
		
		\fbox{\textbf{Answer :}	
			
		\begin{tabular}{|l|r|}
			\hline
				Maximum depth of the tree, $d_{max}$ & 9\\
			\hline
				Number of records in the root vertex, $m$ & 1\\
			\hline
				Average number of record in other vertices, $r$ & 12,51 \\
			\hline
		\end{tabular}}
		

		
			
		\subsection*{Question d}
		
			The minimum depth of a B-tree is obtained when it has its maximum density, i.e. its root and each vertex are full. That condition is met with the following system :
			\begin{displaymath}
				\left\lbrace
				\begin{array}{r c l}	
					m & = & n - 1\\
					r & = & n - 1
				\end{array}
				\right.
			\end{displaymath}
			
			For a B-tree having the above parameters it means $m = r = 21$.
			The minimum depth is given by the following formula :
			\begin{equation}
				d_{min} \geq \dfrac{ln(numberOfRecords + 1)}{ln(r + 1)} - 1
			\end{equation}
			
			Numerical application :
			\begin{displaymath}
				\begin{array}{r c l}
					d_{min} & \geq & \dfrac{ln(3 \times 10^{10} + 1}{ln(21 + 1)} - 1\\
							& \geq & 6,80463665
				\end{array}
			\end{displaymath}
			As $d_{min}$ is an integer, the minimum depth is $d_{min} = 7$.
			
			\subsection*{Question e}
			
			The real value of $r$ for the total number of records per vertex is given by the following formula :\\
		\begin{equation}
			r = \sqrt[d_{min}]{\dfrac{numberOfRecords + 1}{m + 1}} - 1
			\label{eq:avgrecordsmin}
		\end{equation}
		
		Numerical application :\\
		\begin{displaymath}
			r = \sqrt[7]{\dfrac{3 \times 10^{10} + 1}{21 + 1}} - 1 = 19,181662499
		\end{displaymath}
			
			
		\fbox{\textbf{Answer :}	
			
		\begin{tabular}{|l|r|}
			\hline
				Maximum depth of the tree, $d_{min}$ & 7\\
			\hline
				Number of records in the root vertex, $m$ & 21\\
			\hline
				Average number of record in other vertices, $r$ & 19,18 \\
			\hline
		\end{tabular}}
		
		
		
		\subsection*{Question f}
		
			An operating system uses pages to store data. To access data by a pointer, the system will go to the page pointed by the pointer and then operates a shift in that page. To be optimal, a vertex must occupy most of place in a page and it can not be split on two memory pages. So, in 8 gigabytes, we can store 1048576 vertices :
			\begin{displaymath}
				\dfrac{memorySpace}{pageSize} = \dfrac{2^{33}}{8192} = 1048576
			\end{displaymath}
			
			\fbox{
					\textbf{Answer} : we can store 1048576 vertices in 8 gigabytes of memory
			}
			
			